import java.util.*;
public class LRUCache {
  private int capacity;
  private Map<Integer, Integer> cache;
  private LinkedList<Integer> queue;
  // public LRUCache(int capacity) {
  //   this.capacity = capacity;
  //   cache = new HashMap<>();
  //   queue = new LinkedList<>();
  // }
  
  // public int get(int key) { 
  //   if (cache.containsKey(key)) {
  //     queue.remove((Integer) key);
  //     queue.add(key);
  //     return cache.get(key);
  //   }
  //   return -1;
  // }
  // public void put(int key, int value) {
  //   if(cache.containsKey(key)){
  //     cache.remove(key);
  //     queue.remove((Integer) key);
  //   } else if(cache.size() == capacity) {
  //     cache.remove(queue.removeFirst());
  //   }
  //   cache.put(key, value);
  //   queue.add(key);
    
  // }


  public LRUCache(int capacity) {
      this.capacity = capacity;
      cache = new HashMap<>();
      queue = new LinkedList<>();  
  }
    
  public int get(int key) {
      if(cache.containsKey(key)){
        queue.remove((Integer) key);
        queue.add(key);
        return cache.get(key);
    
      }
      return -1;
  }
  
  public void put(int key, int value) {
      if(cache.containsKey(key)){
        queue.remove((Integer) key);
        cache.remove(key);
      } else if(cache.size() == capacity) {
        cache.remove(queue.removeFirst());
      }
      cache.put(key, value);
      queue.add(key);
  }
  

  public static void main(String[] args) { 
    LRUCache cache = new LRUCache(2 /* 缓存容量 */ );
    cache.put(1, 1);
    cache.put(2, 2);
    System.out.println(cache.get(1));       // 1
    cache.put(3, 3);    // 该操作会使得密钥 2 作废
    System.out.println(cache.get(2));       // -1 ()
  }
}



// 设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。

// 它应该支持以下操作： 获取数据 get 和 写入数据 put 。

// 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
// 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

// 示例：

// LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

// cache.put(1, 1);
// cache.put(2, 2);
// cache.get(1);       // 返回  1
// cache.put(3, 3);    // 该操作会使得密钥 2 作废
// cache.get(2);       // 返回 -1 (未找到)
// cache.put(4, 4);    // 该操作会使得密钥 1 作废
// cache.get(1);       // 返回 -1 (未找到)
// cache.get(3);       // 返回  3
// cache.get(4);       // 返回  4